package com.suanfa.jiaoheng;

/**
 * 应该是使用递归或者循环的方式实现比较适合
 */
public class 第1课二分查找 {
    // 算法选择标识
    public static String SELECT_FLAG = "recursionBinarySearch";

    public static void main(String[] args) {
        // 比如要找到3的位置
        int[] numArr = new int[]{1,2,3,4,5,6,7,8};
        // 要查找的目标值
        int targetVal = 3;
        int pos = -1;
        switch(SELECT_FLAG){
            case "recursionBinarySearch":
                pos = recursionBinarySearch(numArr,0,numArr.length-1,targetVal);
                break;
            case "loopBinarySearch":
                pos = loopBinarySearch(numArr,targetVal);
                break;
            default:
                System.out.println("没有找到指定的算法");

        }
        System.out.println("找到的位置是:"+pos);
    }

    public static int recursionBinarySearch(int[] numArr, int startPos, int endPos, int targetVal){
        int pos = -1;
        if(startPos>endPos){
            return pos;
        }
        int halfPos = (startPos+endPos)/2;
        if(numArr[halfPos]<targetVal){
            pos = recursionBinarySearch(numArr,halfPos+1,endPos,targetVal);
        }else if(numArr[halfPos]>targetVal){
            pos = recursionBinarySearch(numArr,startPos,halfPos-1,targetVal);
        }else{
            pos = halfPos;
        }
        return pos;
    }
    // 循环的方式实现
    public static int loopBinarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1; // 如果未找到目标元素，则返回 -1
    }

}

